package Offer;

/**
 * 构建乘积数组
 * 左右乘积列表法
 * @author 是阿秋啊
 * @date 2022/04/23 19:17
 **/
public class Num66 {
    public int[] constructArr(int[] a) {
        int len = a.length;
        if (len == 0) {
            return new int[0];
        }
        int[] ret = new int[len];
        ret[0] = 1;
        // 先从左开始乘
        for (int i = 1; i < len; i++) {
            ret[i] = ret[i - 1] * a[i - 1];
        }
        int temp = 1;
        // 再从右开始乘
        for (int i = len - 2; i >= 0; i--) {
            temp = temp * a[i + 1];
            ret[i] = temp * ret[i];
        }
        // 刚好避过每个下标为i的
        return ret;
    }
}
